package recursion;

import org.junit.Test;

import java.util.Arrays;

/**
 * 最长子序列求和
 *
 * @auth 罗俊华
 * @Date 2022/7/10 1:21 下午
 */
//@Slf4j
public class MaxSequenceSum {


    float[] arr = new float[]{
            1.5F,
            -12.3F,
            3.2F,
            -5.5F,
            23.2F,
            3.2F,
            -1.4F,
            -12.2F,
            34.2F,
            5.4F,
            -7.8F,
            1.1F,
            -4.9F
    };

    int startIndex = 0;
    int endIndex = 0;
    /**
     * startIndex 到 endIndex 之间的和
     */
    float[][] cache;

    float maxSumResult;

    int cacheCount = 0;

    public MaxSequenceSum() {
        cache = new float[arr.length][arr.length];
        for (int i = 0; i < cache.length; i++) {
            Arrays.fill(cache[i], Float.MIN_VALUE);
        }
    }

    private void calculate() {
        for (int right = 0; right < arr.length; right++) {

            for (int left = 0; left < right; left++) {

                float sum = sum(left, right);

                if (sum > maxSumResult) {
                    maxSumResult = sum;
                    startIndex = left;
                    endIndex = right;
                }
            }
        }


    }

    private float sum(int left, int right) {
        float cacheResult = cache[left][right];
        if (Float.compare(Float.MIN_VALUE, cacheResult) != 0) {
            System.out.println("缓存命中，命中次数：" + (cacheCount++) + "：left = " + left + "\tright = " + right + "\t缓存值是：" + cacheResult);
            return cacheResult;
        }
        float result;
        if (left >= right) {
            result = arr[left];
        } else {
            result = arr[left] + sum(left + 1, right);
        }
        cache[left][right] = result;
        return result;
    }

    public float getStartNum() {
        return arr[startIndex];
    }

    public float getEndNum() {
        return arr[endIndex];
    }

    /**
     * 动态规划算法求 最长子序列求和
     */
    @Test
    public void dynamic() {

        MaxSequenceSum h = new MaxSequenceSum();

        h.calculate();

        System.out.println("结果：" + h.startIndex + "~" + h.endIndex + "，总和为：" + h.maxSumResult);
        System.out.println("即：" + h.getStartNum() + "～" + h.getEndNum());
    }
}
